ebab7d0da53c51438720d60c6e2e467c - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>General recursive function</title>

</head>

General recursive function

</h1>

</header>

In <a href="Mathematical_logic" title="Mathematical logic">mathematical logic</a> and <a href="Computer_science" title="Computer science">computer science</a>, a general recursive function, partial recursive function, or μ-recursive function is a <a href="Partial_function" title="Partial function">partial function</a> from <a href="Natural_number" title="Natural number">natural numbers</a> to natural numbers that is "computable" in an intuitive sense – as well as in a <a href="Computable_function" title="Computable function">formal one</a>. If the function is <a href="Total_function" class="mw-redirect" title="Total function">total</a>, it is also called a total recursive function (sometimes shortened to recursive function).<a href="#cite_note-1">[1]</a> In <a href="Computability_theory_(computation)" class="mw-redirect" title="Computability theory (computation)">computability theory</a>, it is shown that the μ-recursive functions are precisely the functions that can be computed by <a href="Turing_machine" title="Turing machine">Turing machines</a><a href="#cite_note-2">[2]</a><a href="#cite_note-4">[4]</a> (this is one of the theorems that supports the <a href="Church%E2%80%93Turing_thesis" title="Church–Turing thesis">Church–Turing thesis</a>). The μ-recursive functions are closely related to <a href="Primitive_recursive_function" title="Primitive recursive function">primitive recursive functions</a>, and their inductive definition (below) builds upon that of the primitive recursive functions. However, not every total recursive function is a primitive recursive function—the most famous example is the <a href="Ackermann_function" title="Ackermann function">Ackermann function</a>.

Other equivalent classes of functions are the functions of <a href="Lambda_calculus" title="Lambda calculus">lambda calculus</a> and the functions that can be computed by <a href="Markov_algorithm" title="Markov algorithm">Markov algorithms</a>.

The subset of all total recursive functions with values in {0,1} is known in <a href="Computational_complexity_theory" title="Computational complexity theory">computational complexity theory</a> as the <a href="R_(complexity)" title="R (complexity)">complexity class R</a>.

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

The μ-recursive functions (or general recursive functions) are partial functions that take finite tuples of natural numbers and return a single natural number. They are the smallest class of partial functions that includes the initial functions and is closed under composition, primitive recursion, and the <a href="%CE%9C_operator" title="Μ operator">minimization operator μ</a>.

The smallest class of functions including the initial functions and closed under composition and primitive recursion (i.e. without minimisation) is the class of <a href="Primitive_recursive_functions" class="mw-redirect" title="Primitive recursive functions">primitive recursive functions</a>. While all primitive recursive functions are total, this is not true of partial recursive functions; for example, the minimisation of the successor function is undefined. The primitive recursive functions are a subset of the total recursive functions, which are a subset of the partial recursive functions. For example, the <a href="Ackermann_function" title="Ackermann function">Ackermann function</a> can be proven to be total recursive, and to be non-primitive.

Primitive or "basic" functions:

<ol><li>Constant functions Ck n: For each natural number n and every k

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mover>

</mrow>

</mrow>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{n}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ n}</annotation>

</semantics>

</math><img src="./c37184786012801a8d6a2123ad2e2af0bd9f5e54.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.488ex; height:3.843ex;" alt="{\displaystyle C_{n}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ n}" loading="lazy"></dd></dl></dd>

<dd>Alternative definitions use instead a zero function as a primitive function that always returns zero, and build the constant functions from the zero function, the successor function and the composition operator.</dd></dl></li>

<li>Successor function S:

<mover>

</mrow>

</mrow>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S(x)\ {\stackrel {\mathrm {def} }{=}}\ x+1\,}</annotation>

</semantics>

</math><img src="./0502d601f23eaffd9591f3bea7633e2984e7e069.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.775ex; height:3.843ex;" alt="{\displaystyle S(x)\ {\stackrel {\mathrm {def} }{=}}\ x+1\,}" loading="lazy"></dd></dl></dd></dl></li>

<li>Projection function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{i}^{k}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{i}^{k}}</annotation>

</semantics>

</math><img src="./361d716d235d131f6d22554b9b4797923c3be3c5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.91ex; height:3.176ex;" alt="{\displaystyle P_{i}^{k}}" loading="lazy"> (also called the Identity function): For all natural numbers <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i,k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i,k}</annotation>

</semantics>

</math><img src="./c3885ba48fa465d00556c235647088efbd248c26.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.048ex; height:2.509ex;" alt="{\displaystyle i,k}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\leq i\leq k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq i\leq k}</annotation>

</semantics>

</math><img src="./83de74da899efbafa01ec98ebf478e9ce5679fc6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.373ex; height:2.343ex;" alt="{\displaystyle 1\leq i\leq k}" loading="lazy">:

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mover>

</mrow>

</mrow>

</mover>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{i}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ x_{i}\,.}</annotation>

</semantics>

</math><img src="./a58359395cd03830e089536be862e42f6bfdd6ef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:21.28ex; height:4.009ex;" alt="{\displaystyle P_{i}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ x_{i}\,.}" loading="lazy"></dd></dl></dd></dl></li></ol>

Operators (the <a href="Domain_of_a_function" title="Domain of a function">domain of a function</a> defined by an operator is the set of the values of the arguments such that every <a href="Function_application" title="Function application">function application</a> that must be done during the computation provides a well-defined result):

<ol><li>Composition operator <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \circ \,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \circ \,}</annotation>

</semantics>

</math><img src="./307536c9e69fa4336e75b99e39243bd02d80f5fd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.55ex; height:1.509ex;" alt="{\displaystyle \circ \,}" loading="lazy"> (also called the substitution operator): Given an m-ary function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h(x_{1},\ldots ,x_{m})\,}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(x_{1},\ldots ,x_{m})\,}</annotation>

</semantics>

</math><img src="./365d0558c7c9c47e4eaa64438fe7f22c5f1f659e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.102ex; height:2.843ex;" alt="{\displaystyle h(x_{1},\ldots ,x_{m})\,}" loading="lazy"> and m k-ary functions <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})}</annotation>

</semantics>

</math><img src="./d08afd5fedccb61860b7a7eadc6e41dd3bf6f5fb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.705ex; height:2.843ex;" alt="{\displaystyle g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})}" loading="lazy">:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mover>

</mrow>

</mrow>

</mover>

</mrow>

<mtext>where</mtext>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h\circ (g_{1},\ldots ,g_{m})\ {\stackrel {\mathrm {def} }{=}}\ f,\quad {\text{where}}\quad f(x_{1},\ldots ,x_{k})=h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})).}</annotation>

</semantics>

</math><img src="./2b56ce2defb5f290d0c486a18ceb62c586ef2835.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:85.457ex; height:3.843ex;" alt="{\displaystyle h\circ (g_{1},\ldots ,g_{m})\ {\stackrel {\mathrm {def} }{=}}\ f,\quad {\text{where}}\quad f(x_{1},\ldots ,x_{k})=h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})).}" loading="lazy"></dd></dl></dd>

<dd>This means that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x_{1},\ldots ,x_{k})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x_{1},\ldots ,x_{k})}</annotation>

</semantics>

</math><img src="./7afedaaa7dfef56c4f5825bc313635b1c6755af3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.068ex; height:2.843ex;" alt="{\displaystyle f(x_{1},\ldots ,x_{k})}" loading="lazy"> is defined only if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}),}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}),}</annotation>

</semantics>

</math><img src="./861f93b042af5f09744c684b3880c755159b2f77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:34.352ex; height:2.843ex;" alt="{\displaystyle g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}),}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}))}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}))}</annotation>

</semantics>

</math><img src="./99146b35be58bcfcd33599483a735fb4b0b91749.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:36.854ex; height:2.843ex;" alt="{\displaystyle h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}))}" loading="lazy"> are all defined.</dd></dl></li>

<li>Primitive recursion operator ρ: Given the k-ary function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x_{1},\ldots ,x_{k})\,}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x_{1},\ldots ,x_{k})\,}</annotation>

</semantics>

</math><img src="./0a070f67fcfdb007cc3bb2afa075fc86722876da.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.293ex; height:2.843ex;" alt="{\displaystyle g(x_{1},\ldots ,x_{k})\,}" loading="lazy"> and k+2 -ary function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h(y,z,x_{1},\ldots ,x_{k})\,}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(y,z,x_{1},\ldots ,x_{k})\,}</annotation>

</semantics>

</math><img src="./f7854e20a91c28109d5fcc4c6ba29477f01858d1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.827ex; height:2.843ex;" alt="{\displaystyle h(y,z,x_{1},\ldots ,x_{k})\,}" loading="lazy">:

<mtr>

<mtd>

</mtd>

<mtd>

<mover>

</mrow>

</mrow>

</mover>

</mrow>

<mtext>where the k+1 -ary function </mtext>

</mrow>

<mtext> is defined by</mtext>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\rho (g,h)&\ {\stackrel {\mathrm {def} }{=}}\ f\quad {\text{where the k+1 -ary function }}f{\text{ is defined by}}\\f(0,x_{1},\ldots ,x_{k})&=g(x_{1},\ldots ,x_{k})\\f(S(y),x_{1},\ldots ,x_{k})&=h(y,f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})\,.\end{aligned}}}</annotation>

</semantics>

</math><img src="./242b75ebc276ba9000aad50314ddad11bb9de311.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.505ex; width:69.431ex; height:10.176ex;" alt="{\displaystyle {\begin{aligned}\rho (g,h)&\ {\stackrel {\mathrm {def} }{=}}\ f\quad {\text{where the k+1 -ary function }}f{\text{ is defined by}}\\f(0,x_{1},\ldots ,x_{k})&=g(x_{1},\ldots ,x_{k})\\f(S(y),x_{1},\ldots ,x_{k})&=h(y,f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})\,.\end{aligned}}}" loading="lazy"></dd></dl></dd>

<dd>This means that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(y,x_{1},\ldots ,x_{k})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(y,x_{1},\ldots ,x_{k})}</annotation>

</semantics>

</math><img src="./11366122df75930c4b03478bede4430487264142.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.258ex; height:2.843ex;" alt="{\displaystyle f(y,x_{1},\ldots ,x_{k})}" loading="lazy"> is defined only if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x_{1},\ldots ,x_{k})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x_{1},\ldots ,x_{k})}</annotation>

</semantics>

</math><img src="./3e0c0e005a76b84a7c5df63c0cfcb7a3be0e9a62.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.906ex; height:2.843ex;" alt="{\displaystyle g(x_{1},\ldots ,x_{k})}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h(z,f(z,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(z,f(z,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})}</annotation>

</semantics>

</math><img src="./41262cb79bab954bcd364956600d0eeb8ff6dfaf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.475ex; height:2.843ex;" alt="{\displaystyle h(z,f(z,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})}" loading="lazy"> are defined for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z<y.}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z<y.}</annotation>

</semantics>

</math><img src="./3b917e5a7ec497f26414cc219cf550bf075c3486.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.989ex; height:2.176ex;" alt="{\displaystyle z<y.}" loading="lazy"></dd></dl></li>

<li>Minimization operator μ: Given a (k+1)-ary function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(y,x_{1},\ldots ,x_{k})\,}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(y,x_{1},\ldots ,x_{k})\,}</annotation>

</semantics>

</math><img src="./bb61740f1309227e273567a96c7df63d4ce4b1e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.645ex; height:2.843ex;" alt="{\displaystyle f(y,x_{1},\ldots ,x_{k})\,}" loading="lazy">, the k-ary function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu (f)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu (f)}</annotation>

</semantics>

</math><img src="./67af7831bda101ac64505297da4c316104433e5f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.49ex; height:2.843ex;" alt="{\displaystyle \mu (f)}" loading="lazy"> is defined by:

<dl><dd><dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}\mu (f)(x_{1},\ldots ,x_{k})=z{\stackrel {\mathrm {def} }{\iff }}\ f(i,x_{1},\ldots ,x_{k})&>0\quad {\text{for}}\quad i=0,\ldots ,z-1\quad {\text{and}}\\f(z,x_{1},\ldots ,x_{k})&=0\quad \end{aligned}}}">

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mover>

</mrow>

</mrow>

</mover>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\mu (f)(x_{1},\ldots ,x_{k})=z{\stackrel {\mathrm {def} }{\iff }}\ f(i,x_{1},\ldots ,x_{k})&>0\quad {\text{for}}\quad i=0,\ldots ,z-1\quad {\text{and}}\\f(z,x_{1},\ldots ,x_{k})&=0\quad \end{aligned}}}</annotation>

</semantics>

</math><img src="./2ed05f72c426b147ff72e154987649de7855a176.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:75.404ex; height:7.176ex;" alt="{\displaystyle {\begin{aligned}\mu (f)(x_{1},\ldots ,x_{k})=z{\stackrel {\mathrm {def} }{\iff }}\ f(i,x_{1},\ldots ,x_{k})&>0\quad {\text{for}}\quad i=0,\ldots ,z-1\quad {\text{and}}\\f(z,x_{1},\ldots ,x_{k})&=0\quad \end{aligned}}}" loading="lazy"></dd></dl></dd></dl></li></ol>

Intuitively, minimisation seeks—beginning the search from 0 and proceeding upwards—the smallest argument that causes the function to return zero; if there is no such argument, or if one encounters an argument for which f is not defined, then the search never terminates, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu (f)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu (f)}</annotation>

</semantics>

</math><img src="./67af7831bda101ac64505297da4c316104433e5f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.49ex; height:2.843ex;" alt="{\displaystyle \mu (f)}" loading="lazy"> is not defined for the argument <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{1},\ldots ,x_{k}).}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{1},\ldots ,x_{k}).}</annotation>

</semantics>

</math><img src="./59393f3d8b20a91b637df2af661f97a241cbb847.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.437ex; height:2.843ex;" alt="{\displaystyle (x_{1},\ldots ,x_{k}).}" loading="lazy">

While some textbooks use the μ-operator as defined here,<a href="#cite_note-Enderton.1972-5">[5]</a><a href="#cite_note-Boolos.Burgess.Jeffrey.2007-6">[6]</a> others<a href="#cite_note-Jones.1997-7">[7]</a><a href="#cite_note-8">[8]</a> demand that the μ-operator is applied to total functions f only. Although this restricts the μ-operator as compared to the definition given here, the class of μ-recursive functions remains the same, which follows from Kleene's Normal Form Theorem (see <a href="#Normal_form_theorem">below</a>).<a href="#cite_note-Enderton.1972-5">[5]</a><a href="#cite_note-Boolos.Burgess.Jeffrey.2007-6">[6]</a> The only difference is, that it becomes undecidable whether a specific function definition defines a μ-recursive function, as it is undecidable whether a computable (i.e. μ-recursive) function is total.<a href="#cite_note-Jones.1997-7">[7]</a>

The <a href="Strong_equality" class="mw-redirect" title="Strong equality">strong equality</a> relation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \simeq }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \simeq }</annotation>

</semantics>

</math><img src="./65b9738551241417d16d9843525ed52410af4dc9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.081ex; margin-bottom: -0.253ex; width:1.808ex; height:1.509ex;" alt="{\displaystyle \simeq }" loading="lazy"> can be used to compare partial μ-recursive functions. This is defined for all partial functions f and g so that

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x_{1},\ldots ,x_{k})\simeq g(x_{1},\ldots ,x_{l})}</annotation>

</semantics>

</math><img src="./095f1fa231f917f18888521d6d1da2b6083356bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.706ex; height:2.843ex;" alt="{\displaystyle f(x_{1},\ldots ,x_{k})\simeq g(x_{1},\ldots ,x_{l})}" loading="lazy"></dd></dl>

holds <a href="If_and_only_if" title="If and only if">if and only if</a> for any choice of arguments either both functions are defined and their values are equal or both functions are undefined.

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

Examples not involving the minimization operator can be found at <a href="Primitive_recursive_function#Examples" title="Primitive recursive function">Primitive recursive function#Examples</a>.

The following examples are intended just to demonstrate the use of the minimization operator; they could also be defined without it, albeit in a more complicated way, since they are all primitive recursive.

<div><ul><li>The <a href="Integer_square_root" title="Integer square root">integer square root</a> of x can be defined as the least z such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (z+1)^{2}>x}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (z+1)^{2}>x}</annotation>

</semantics>

</math><img src="./eaf380ddb4646a054e28d31209ce18ee5d51d170.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.383ex; height:3.176ex;" alt="{\displaystyle (z+1)^{2}>x}" loading="lazy">. Using the minimization operator, a general recursive definition is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \operatorname {Isqrt} =\mu (\operatorname {Not} \circ \operatorname {Gt} \circ (\operatorname {Mul} \circ (S\circ P_{1}^{2},S\circ P_{1}^{2}),P_{2}^{2}))}">

<mi>Isqrt</mi>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {Isqrt} =\mu (\operatorname {Not} \circ \operatorname {Gt} \circ (\operatorname {Mul} \circ (S\circ P_{1}^{2},S\circ P_{1}^{2}),P_{2}^{2}))}</annotation>

</semantics>

</math><img src="./f9a9ac568eafc9540442bcb86c1192d22083f2ff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:48.456ex; height:3.176ex;" alt="{\displaystyle \operatorname {Isqrt} =\mu (\operatorname {Not} \circ \operatorname {Gt} \circ (\operatorname {Mul} \circ (S\circ P_{1}^{2},S\circ P_{1}^{2}),P_{2}^{2}))}" loading="lazy">, where Not, Gt, and Mul are <a href="Logical_negation" class="mw-redirect" title="Logical negation">logical negation</a>, greater-than, and multiplication,<a href="#cite_note-9">[9]</a> respectively. In fact, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\operatorname {Not} \circ \operatorname {Gt} \circ (\operatorname {Mul} \circ (S\circ P_{1}^{2},S\circ P_{1}^{2}),P_{2}^{2}))\;(z,x)=(\lnot S(z)*S(z)>x)}">

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\operatorname {Not} \circ \operatorname {Gt} \circ (\operatorname {Mul} \circ (S\circ P_{1}^{2},S\circ P_{1}^{2}),P_{2}^{2}))\;(z,x)=(\lnot S(z)*S(z)>x)}</annotation>

</semantics>

</math><img src="./0bc6d06e54462d1dd16c85a33656cec2f19506fb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:66.937ex; height:3.176ex;" alt="{\displaystyle (\operatorname {Not} \circ \operatorname {Gt} \circ (\operatorname {Mul} \circ (S\circ P_{1}^{2},S\circ P_{1}^{2}),P_{2}^{2}))\;(z,x)=(\lnot S(z)*S(z)>x)}" loading="lazy"> is 0 if, and only if, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S(z)*S(z)>x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S(z)*S(z)>x}</annotation>

</semantics>

</math><img src="./2a70c74845378dd52f13b0087ff923e66eb71153.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.416ex; height:2.843ex;" alt="{\displaystyle S(z)*S(z)>x}" loading="lazy"> holds. Hence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \operatorname {Isqrt} (x)}">

<mi>Isqrt</mi>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {Isqrt} (x)}</annotation>

</semantics>

</math><img src="./78b2c2a2126c3bb4b4be8ea77fdab732b3763c47.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.939ex; height:2.843ex;" alt="{\displaystyle \operatorname {Isqrt} (x)}" loading="lazy"> is the least z such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S(z)*S(z)>x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S(z)*S(z)>x}</annotation>

</semantics>

</math><img src="./2a70c74845378dd52f13b0087ff923e66eb71153.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.416ex; height:2.843ex;" alt="{\displaystyle S(z)*S(z)>x}" loading="lazy"> holds. The negation <a href="Junctor" title="Junctor">junctor</a> Not is needed since Gt encodes truth by 1, while μ seeks for 0.</li></ul></div>

The following examples define general recursive functions that are not primitive recursive; hence they cannot avoid using the minimization operator.

<div class="mw-heading mw-heading2"><h2 id="Total_recursive_function">Total recursive function</h2></div>

A general recursive function is called total recursive function if it is defined for every input, or, equivalently, if it can be computed by a <a href="Total_Turing_machine" class="mw-redirect" title="Total Turing machine">total Turing machine</a>. There is no way to computably tell if a given general recursive function is total - see <a href="Halting_problem" title="Halting problem">Halting problem</a>.

<div class="mw-heading mw-heading2"><h2 id="Equivalence_with_other_models_of_computability">Equivalence with other models of computability</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

In the <a href="Church's_thesis" class="mw-redirect" title="Church's thesis">equivalence of models of computability</a>, a parallel is drawn between <a href="Turing_machine" title="Turing machine">Turing machines</a> that do not terminate for certain inputs and an undefined result for that input in the corresponding partial recursive function.

The unbounded search operator is not definable by the rules of primitive recursion as those do not provide a mechanism for "infinite loops" (undefined values).

<div class="mw-heading mw-heading2"><h2 id="Normal_form_theorem">Normal form theorem</h2></div>

A <a href="Kleene's_T_predicate#Normal_form_theorem" title="Kleene's T predicate">normal form theorem</a> due to Kleene says that for each k there are primitive recursive functions <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U(y)\!}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U(y)\!}</annotation>

</semantics>

</math><img src="./3bd265d7fd8cc27662e78aca29cce78e22695e86.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-right: -0.166ex; width:4.527ex; height:2.843ex;" alt="{\displaystyle U(y)\!}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T(y,e,x_{1},\ldots ,x_{k})\!}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T(y,e,x_{1},\ldots ,x_{k})\!}</annotation>

</semantics>

</math><img src="./c5cf737b01b6d3b1ab1ab247eb6de62d3d6333a1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-right: -0.166ex; width:17.512ex; height:2.843ex;" alt="{\displaystyle T(y,e,x_{1},\ldots ,x_{k})\!}" loading="lazy"> such that for any μ-recursive function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x_{1},\ldots ,x_{k})\!}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x_{1},\ldots ,x_{k})\!}</annotation>

</semantics>

</math><img src="./030840a66076bec37f03ff404b6b4d6e1ced5929.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-right: -0.166ex; width:12.848ex; height:2.843ex;" alt="{\displaystyle f(x_{1},\ldots ,x_{k})\!}" loading="lazy"> with k free variables there is an e such that

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x_{1},\ldots ,x_{k})\simeq U(\mu (T)(e,x_{1},\ldots ,x_{k}))}</annotation>

</semantics>

</math><img src="./309cc4ee3ddda3b3080f3fec16d0b119d8463a85.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:38.513ex; height:2.843ex;" alt="{\displaystyle f(x_{1},\ldots ,x_{k})\simeq U(\mu (T)(e,x_{1},\ldots ,x_{k}))}" loading="lazy">.</dd></dl>

The number e is called an index or <a href="G%C3%B6del_number" class="mw-redirect" title="Gödel number">Gödel number</a> for the function f.<a href="#cite_note-10">[10]</a>: 52–53 A consequence of this result is that any μ-recursive function can be defined using a single instance of the μ operator applied to a (total) primitive recursive function.

<a href="Marvin_Minsky" title="Marvin Minsky">Minsky</a> observes the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U}</annotation>

</semantics>

</math><img src="./458a728f53b9a0274f059cd695e067c430956025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.783ex; height:2.176ex;" alt="{\displaystyle U}" loading="lazy"> defined above is in essence the μ-recursive equivalent of the <a href="Universal_Turing_machine" title="Universal Turing machine">universal Turing machine</a>:

/* start https://en.wikipedia.org/ */

.mw-parser-output .templatequote{overflow:hidden;margin:1em 0;padding:0 32px}.mw-parser-output .templatequotecite{line-height:1.5em;text-align:left;margin-top:0}@media(min-width:500px){.mw-parser-output .templatequotecite{padding-left:1.6em}}

/* end https://en.wikipedia.org/ */

</style><blockquote class="templatequote">To construct U is to write down the definition of a general-recursive function U(n, x) that correctly interprets the number n and computes the appropriate function of x. to construct U directly would involve essentially the same amount of effort, and essentially the same ideas, as we have invested in constructing the universal Turing machine <a href="#cite_note-FOOTNOTEMinsky1972189-11">[11]</a></blockquote>

<div class="mw-heading mw-heading2"><h2 id="Symbolism">Symbolism</h2></div>

A number of different symbolisms are used in the literature. An advantage to using the symbolism is a derivation of a function by "nesting" of the operators one inside the other is easier to write in a compact form. In the following the string of parameters x1, ..., xn is abbreviated as x:

<ul><li>Constant function: Kleene uses " Cn q(x) = q " and Boolos-Burgess-Jeffrey (2002) (B-B-J) use the abbreviation " constn( x) = n ":</li></ul>

<dd>e.g. const13 ( r, s, t, u, v, w, x ) = 13</dd></dl></dd></dl>

<ul><li>Successor function: Kleene uses x' and S for "Successor". As "successor" is considered to be primitive, most texts use the apostrophe as follows:</li></ul>

<dl><dd><dl><dd>S(a) = a +1 =def a', where 1 =def 0', 2 =def 0 ' ', etc.</dd></dl></dd></dl>

<ul><li>Identity function: Kleene (1952) uses " Un i " to indicate the <a href="Identity_function" title="Identity function">identity function</a> over the variables xi; B-B-J use the identity function idn i over the variables x1 to xn:</li></ul>

<ul><li>Composition (Substitution) operator: Kleene uses a bold-face Sm n (not to be confused with his S for "successor" ! ). The superscript "m" refers to the mth of function "fm", whereas the subscript "n" refers to the nth variable "xn":</li></ul>

<dl><dd>If we are given h( x )= g( f1(x), ... , fm(x) )

<dl><dd>In a similar manner, but without the sub- and superscripts, B-B-J write:

<ul><li>Primitive Recursion: Kleene uses the symbol " Rn(base step, induction step) " where n indicates the number of variables, B-B-J use " Pr(base step, induction step)(x)". Given:</li></ul>

<li>induction step: h( y+1, x ) = g( y, h(y, x),x )</li></ul></dd></dl>

<dl><dd>Example: primitive recursion definition of a + b:

<li>induction step: f( b' , a ) = ( f ( b, a ) )' = g( b, f( b, a), a ) = g( b, c, a ) = c' = S(U3 2( b, c, a ))</li></ul>

Example: Kleene gives an example of how to perform the recursive derivation of f(b, a) = b + a (notice reversal of variables a and b). He starts with 3 initial functions

<dl><dd>induction step: h( b', a ) = g( b, h( b, a ), a )</dd></dl></dd></dl>

He arrives at:

<div class="mw-heading mw-heading2"><h2 id="Examples_2">Examples</h2></div>

<ul><li><a href="Fibonacci_number" class="mw-redirect" title="Fibonacci number">Fibonacci number</a></li>

<li><a href="McCarthy_91_function" title="McCarthy 91 function">McCarthy 91 function</a></li></ul>

<ul><li><a href="Recursion_theory" class="mw-redirect" title="Recursion theory">Recursion theory</a></li>

<li><a href="Recursion" title="Recursion">Recursion</a></li>

<li><a href="Recursion_(computer_science)" title="Recursion (computer science)">Recursion (computer science)</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation book cs1"><a rel="nofollow" class="external text" href="https://plato.stanford.edu/entries/recursive-functions/#PartRecuFuncPartRecuFuncREC">"Recursive Functions"</a>. The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University. 2021.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <a href="Stanford_Encyclopedia_of_Philosophy" title="Stanford Encyclopedia of Philosophy">Stanford Encyclopedia of Philosophy</a>, Entry <a rel="nofollow" class="external text" href="http://plato.stanford.edu/entries/recursive-functions">Recursive Functions</a>, Sect.1.7: "[The class of μ-recursive functions] turns out to coincide with the class of the Turing-computable functions introduced by Alan Turing as well as with the class of the λ-definable functions introduced by Alonzo Church."

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFKleene1936" class="citation journal cs1"><a href="Stephen_C._Kleene" class="mw-redirect" title="Stephen C. Kleene">Kleene, Stephen C.</a> (1936). <a rel="nofollow" class="external text" href="https://projecteuclid.org/euclid.dmj/1077489488">"λ-definability and recursiveness"</a>. <a href="Duke_Mathematical_Journal" title="Duke Mathematical Journal">Duke Mathematical Journal</a>. 2 (2): 340–352. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1215%2Fs0012-7094-36-00227-2">10.1215/s0012-7094-36-00227-2</a>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFTuring1937" class="citation journal cs1"><a href="Alan_Turing" title="Alan Turing">Turing, Alan Mathison</a> (Dec 1937). "Computability and λ-Definability". <a href="Journal_of_Symbolic_Logic" title="Journal of Symbolic Logic">Journal of Symbolic Logic</a>. 2 (4): 153–163. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2268280">10.2307/2268280</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2268280">2268280</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2317046">2317046</a>.</cite> Proof outline on p.153: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda {\mbox{-definable}}}">

<mtext>-definable</mtext>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda {\mbox{-definable}}}</annotation>

</semantics>

</math><img src="./7d6c738af9eca0d38afefb0086eeda0af4e847dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:11.24ex; height:2.176ex;" alt="{\displaystyle \lambda {\mbox{-definable}}}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\stackrel {triv}{\implies }}}">

<mover>

</mrow>

</mrow>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\stackrel {triv}{\implies }}}</annotation>

</semantics>

</math><img src="./b351515c182febf6ac8e0776971a5d59bacd3eb6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.096ex; height:3.676ex;" alt="{\displaystyle {\stackrel {triv}{\implies }}}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda {\mbox{-}}K{\mbox{-definable}}}">

</mstyle>

</mrow>

<mtext>-definable</mtext>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda {\mbox{-}}K{\mbox{-definable}}}</annotation>

</semantics>

</math><img src="./cb207a7d1eda3e4427dad70b3ba764ca15f5acd3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:14.081ex; height:2.176ex;" alt="{\displaystyle \lambda {\mbox{-}}K{\mbox{-definable}}}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\stackrel {160}{\implies }}}">

<mover>

</mrow>

</mrow>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\stackrel {160}{\implies }}}</annotation>

</semantics>

</math><img src="./70829859183c6c699fa6ec613d9311e293b816ba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.096ex; height:3.676ex;" alt="{\displaystyle {\stackrel {160}{\implies }}}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mbox{Turing computable}}}">

<mtext>Turing computable</mtext>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mbox{Turing computable}}}</annotation>

</semantics>

</math><img src="./3084223de52f82cad93553f677a206c2957b06f6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:19.319ex; height:2.509ex;" alt="{\displaystyle {\mbox{Turing computable}}}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\stackrel {161}{\implies }}}">

<mover>

</mrow>

</mrow>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\stackrel {161}{\implies }}}</annotation>

</semantics>

</math><img src="./2873e188be2ba5438ac119acbe19f3f216db723d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.096ex; height:3.676ex;" alt="{\displaystyle {\stackrel {161}{\implies }}}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu {\mbox{-recursive}}}">

<mtext>-recursive</mtext>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu {\mbox{-recursive}}}</annotation>

</semantics>

</math><img src="./2c2208f29f466cfa33360598507960c4cedd32c7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.18ex; height:2.676ex;" alt="{\displaystyle \mu {\mbox{-recursive}}}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\stackrel {Kleene}{\implies }}}">

<mover>

</mrow>

</mrow>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\stackrel {Kleene}{\implies }}}</annotation>

</semantics>

</math><img src="./ffc36b8d9792097493bd8b7fb37cf21e82dceaed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.236ex; height:3.676ex;" alt="{\displaystyle {\stackrel {Kleene}{\implies }}}" loading="lazy"><a href="#cite_note-3">[3]</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda {\mbox{-definable}}}">

<mtext>-definable</mtext>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda {\mbox{-definable}}}</annotation>

</semantics>

</math><img src="./7d6c738af9eca0d38afefb0086eeda0af4e847dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:11.24ex; height:2.176ex;" alt="{\displaystyle \lambda {\mbox{-definable}}}" loading="lazy">

</li>

<li id="cite_note-Enderton.1972-5">^ <a href="#cite_ref-Enderton.1972_5-0">a</a> <a href="#cite_ref-Enderton.1972_5-1">b</a> Enderton, H. B., A Mathematical Introduction to Logic, Academic Press, 1972

</li>

<li id="cite_note-Boolos.Burgess.Jeffrey.2007-6">^ <a href="#cite_ref-Boolos.Burgess.Jeffrey.2007_6-0">a</a> <a href="#cite_ref-Boolos.Burgess.Jeffrey.2007_6-1">b</a> Boolos, G. S., Burgess, J. P., Jeffrey, R. C., Computability and Logic, Cambridge University Press, 2007

</li>

<li id="cite_note-Jones.1997-7">^ <a href="#cite_ref-Jones.1997_7-0">a</a> <a href="#cite_ref-Jones.1997_7-1">b</a> Jones, N. D., Computability and Complexity: From a Programming Perspective, The MIT Press, Cambridge, Massachusetts, London, England, 1997

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> Kfoury, A. J., R. N. Moll, and M. A. Arbib, A Programming Approach to Computability, 2nd ed., Springer-Verlag, Berlin, Heidelberg, New York, 1982

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> defined in <a href="Primitive_recursive_function#Junctors" title="Primitive recursive function">Primitive recursive function#Junctors</a>, <a href="Primitive_recursive_function#Equality_predicate" title="Primitive recursive function">Primitive recursive function#Equality predicate</a>, and <a href="Primitive_recursive_function#Multiplication" title="Primitive recursive function">Primitive recursive function#Multiplication</a>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFStephen_Cole_Kleene1943" class="citation journal cs1">Stephen Cole Kleene (Jan 1943). <a rel="nofollow" class="external text" href="https://www.ams.org/journals/tran/1943-053-01/S0002-9947-1943-0007371-8/S0002-9947-1943-0007371-8.pdf">"Recursive predicates and quantifiers"</a> (PDF). Transactions of the American Mathematical Society. 53 (1): 41–73. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0002-9947-1943-0007371-8">10.1090/S0002-9947-1943-0007371-8</a>.</cite>

</li>

<li id="cite_note-FOOTNOTEMinsky1972189-11"><a href="#cite_ref-FOOTNOTEMinsky1972189_11-0">^</a> <a href="#CITEREFMinsky1972">Minsky 1972</a>, pp. 189.

</li>

</ol></div></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}

/* end https://en.wikipedia.org/ */

</style><div class="refbegin" style="">

<ul><li><cite id="CITEREFKleene1991" class="citation book cs1"><a href="Stephen_Kleene" class="mw-redirect" title="Stephen Kleene">Kleene, Stephen</a> (1991) [1952]. Introduction to Metamathematics. Walters-Noordhoff & North-Holland. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-7204-2103-9</bdi>.</cite></li>

<li><cite id="CITEREFSoare1999" class="citation book cs1">Soare, R. (1999) [1987]. <a rel="nofollow" class="external text" href="https://books.google.com/books?id=9I7Pl00LU5gC&pg=PP1">Recursively enumerable sets and degrees: A Study of Computable Functions and Computably Generated Sets</a>. Springer-Verlag. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783540152996</bdi>.</cite></li>

<li><cite id="CITEREFMinsky1972" class="citation book cs1"><a href="Marvin_L._Minsky" class="mw-redirect" title="Marvin L. Minsky">Minsky, Marvin L.</a> (1972) [1967]. Computation: Finite and Infinite Machines. Prentice-Hall. pp. 210–5. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780131654495</bdi>.</cite></li></ul>

<dl><dd>On pages 210-215 Minsky shows how to create the μ-operator using the <a href="Register_machine" title="Register machine">register machine</a> model, thus demonstrating its equivalence to the general recursive functions.</dd></dl>

<ul><li><cite id="CITEREFBoolosBurgessJeffrey2002" class="citation book cs1"><a href="George_Boolos" title="George Boolos">Boolos, George</a>; <a href="John_P._Burgess" title="John P. Burgess">Burgess, John</a>; <a href="Richard_Jeffrey" title="Richard Jeffrey">Jeffrey, Richard</a> (2002). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=0LpsXQV2kXAC&pg=PA70">"6.2 Minimization"</a>. Computability and Logic (4th ed.). Cambridge University Press. pp. 70–71. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780521007580</bdi>.</cite></li></ul>

</div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://plato.stanford.edu/entries/recursive-functions/">Stanford Encyclopedia of Philosophy entry</a></li>

<li><a rel="nofollow" class="external text" href="http://people.irisa.fr/Francois.Schwarzentruber/recursive_functions_to_turing_machines/">A compiler for transforming a recursive function into an equivalent Turing machine</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1038841319">

/* start https://en.wikipedia.org/ */

.mw-parser-output .tooltip-dotted{border-bottom:1px dotted;cursor:help}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox authority-control" aria-labelledby="Authority_control_databases_frameless&#124;text-top&#124;10px&#124;alt=Edit_this_at_Wikidata&#124;link=https&#58;//www.wikidata.org/wiki/Q284164#identifiers&#124;class=noprint&#124;Edit_this_at_Wikidata1399" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Authority_control_databases_frameless&#124;text-top&#124;10px&#124;alt=Edit_this_at_Wikidata&#124;link=https&#58;//www.wikidata.org/wiki/Q284164#identifiers&#124;class=noprint&#124;Edit_this_at_Wikidata1399" style="font-size:114%;margin:0 4em">Authority control databases </div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">National</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><a rel="nofollow" class="external text" href="https://id.loc.gov/authorities/sh85112014">United States</a></li><li><a rel="nofollow" class="external text" href="https://catalogue.bnf.fr/ark:/12148/cb11977577z">France</a></li><li><a rel="nofollow" class="external text" href="https://data.bnf.fr/ark:/12148/cb11977577z">BnF data</a></li><li><a rel="nofollow" class="external text" href="https://kopkatalogs.lv/F?func=direct&local_base=lnc10&doc_number=000165558&P_CON_LNG=ENG">Latvia</a></li><li><a rel="nofollow" class="external text" href="https://www.nli.org.il/en/authorities/987007565763305171">Israel</a></li></ul></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><a rel="nofollow" class="external text" href="https://lux.collections.yale.edu/view/concept/6e1406ae-cc27-4d78-a61e-87d5e157c119">Yale LUX</a></li></ul></div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-29" href="https://en.wikipedia.org/wiki/?title=General_recursive_function&oldid=1303228064">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>